#include "Polynomial.h"

// 初始化多项式
Polynomial* InitPolynomial()
{
    Polynomial* p = (Polynomial*)malloc(sizeof(Polynomial));
    if (NULL == p)
    {
        return NULL;
    }
    p->variable = 0;
    p->ptr = (PolyNode*)malloc(sizeof(PolyNode));
    if (NULL == p->ptr)
    {
        free(p);
        return NULL;
    }
    p->ptr->coe = 0;
    p->ptr->deg = 0;
    p->ptr->next = NULL;
    return p;
}

// 析构多项式内的链表
void base_DeletePolynomial(PolyNode* pnode)
{
    if (NULL == pnode->next)
    {
        return;
    }
    else
    {
        base_DeletePolynomial(pnode->next);
        free(pnode);
    }
}

// 析构多项式
void DeletePolynomial(Polynomial* p)
{
    base_DeletePolynomial(p->ptr);
    free(p);
}

// 向多项式中插入元素,保证次数递减
void InsertToPolynomial(Polynomial* p, int coe, int deg)
{
    PolyNode* ptr = p->ptr;
    for (; NULL != ptr->next; ptr = ptr->next)
    {
        // 如果存在次数相同,把系数直接相加
        if (ptr->next->deg == deg)
        {
            ptr->next->coe += coe;
            return;
        }
        // 如果当前项的次数比要插入的项次数小,就插在当前项前面
        else if (ptr->next->deg < deg)
        {
            PolyNode* node = (PolyNode*)malloc(sizeof(PolyNode));
            if (NULL == node)
            {
                return;
            }
            node->coe = coe;
            node->deg = deg;
            node->next = ptr->next;
            ptr->next = node;
            return;
        }
        // 如果当前项的次数比要插入的项次数大,向后寻找直到存在次数相同或次数更小
    }
    // 此时说明要插入的项是次数最小的一项
    PolyNode* node = (PolyNode*)malloc(sizeof(PolyNode));
    if (NULL == node)
    {
        return;
    }
    node->coe = coe;
    node->deg = deg;
    node->next = NULL;
    ptr->next = node;
}

// 判断是否为变量
int IsVariable(char ch)
{
    return !isdigit(ch) && ch != '+' && ch != '-' && ch != '^';
}

// 判断是否为数字
int IsDigit(char ch)
{
    return isdigit(ch);
}

// 判断是否为操作符
int IsOperator(char ch)
{
    return ch == '+' || ch == '-';
}

// 判断是否为指数符
int IsDegree(char ch)
{
    return ch == '^';
}

// 用字符串给多项式赋值,成功返回1,失败返回0
int SetPolynomial(Polynomial* p, const char* s)
{
    int len = strlen(s);
    int is_deg = 0; // 确认当前是否为指数部分
    int is_var = 0; // 确认当前是否为变量
    int coe = 0; // 保存当前系数
    int deg = 0; // 保存当前指数
    int f = 1; // 判断正负用,最终系数=coe*f
    char ch;
    for (int i = 0; i <= len; i++)
    {
        if (i != len)
        {
            ch = s[i];
        }
        if (i == len || IsOperator(ch))
        {
            if (i == len - 1)
            {
                // 操作符结尾
                return 0;
            }
            if (IsOperator(ch) && s[i - 1] == '^')
            {
                // ^在操作符前一个
                return 0;
            }
            // 如果是开头的负号
            if (i == 0)
            {
                if (ch == '+')
                {
                    return 0;
                }
                else
                {
                    f = -1;
                }
            }
            // 否则说明是多项式中间隔项的操作符
            else
            {
                // 说明上一项是常量
                if (-1 == is_var)
                {
                    InsertToPolynomial(p, coe * f, 0);
                }
                // 说明上一项是变量
                else if (1 == is_var)
                {
                    InsertToPolynomial(p, coe == 0 ? 1 * f : coe * f, deg == 0 ? 1 : deg);
                }
                // 说明有问题
                else
                {
                    return 0;
                }
                is_deg = 0;
                is_var = 0;
                coe = 0;
                deg = 0;
                f = ch == '+' ? 1 : -1;
            }
        }
        else if (IsDigit(ch))
        {
            // 如果不是指数
            if (!is_deg)
            {
                // 如果前面出现了变量
                if (1 == is_var)
                {
                    return 0;
                }
                is_var = -1;
                coe = coe * 10 + (ch ^ 48);
            }
            // 如果是指数
            else
            {
                // 如果前面未出现变量
                if (1 != is_var)
                {
                    return 0;
                }
                deg = deg * 10 + (ch ^ 48);
            }
        }
        else if (IsVariable(ch))
        {
            if (p->variable == 0)
            {
                p->variable = ch;
            }
            is_var = 1;
        }
        else if (IsDegree(ch))
        {
            if (i == len - 1)
            {
                // 指数符号结尾
                return 0;
            }
            if (1 != is_var)
            {
                return 0;
            }
            is_deg = 1;
        }
        else
        {
            return 0;
        }
    }
    return 1;
}

// 多项式求和(需要析构返回值)
Polynomial* AddPolynomial(Polynomial* a, Polynomial* b)
{
    Polynomial* p = InitPolynomial();
    if (a->variable != 0)
    {
         p->variable = a->variable;
    }
    else
    {
        p->variable = b->variable;
    }
    PolyNode* ptra = a->ptr;
    PolyNode* ptrb = b->ptr;
    while (ptra->next != NULL && ptrb->next != NULL)
    {
        if (ptra->next->deg == ptrb->next->deg)
        {
            InsertToPolynomial(p, ptra->next->coe + ptrb->next->coe, ptra->next->deg);
            ptra = ptra->next;
            ptrb = ptrb->next;
        }
        else if (ptra->next->deg > ptrb->next->deg)
        {
            InsertToPolynomial(p, ptra->next->coe, ptra->next->deg);
            ptra = ptra->next;
        }
        else
        {
            InsertToPolynomial(p, ptrb->next->coe, ptrb->next->deg);
            ptrb = ptrb->next;
        }
    }
    while (ptra->next != NULL)
    {
        InsertToPolynomial(p, ptra->next->coe, ptra->next->deg);
        ptra = ptra->next;
    }
    while (ptrb->next != NULL)
    {
        InsertToPolynomial(p, ptrb->next->coe, ptrb->next->deg);
        ptrb = ptrb->next;
    }
    return p;
}

// 多项式求积(需要析构返回值)
Polynomial* MultPolynomial(Polynomial* a, Polynomial* b)
{
    Polynomial* p = InitPolynomial();
    if (a->variable != 0)
    {
         p->variable = a->variable;
    }
    else
    {
        p->variable = b->variable;
    }
    for (PolyNode* ptra = a->ptr; ptra->next != NULL; ptra = ptra->next)
    {
        for (PolyNode* ptrb = b->ptr; ptrb->next != NULL; ptrb = ptrb->next)
        {
            InsertToPolynomial(p, ptra->next->coe * ptrb->next->coe, ptra->next->deg + ptrb->next->deg);
        }
    }
    return p;
}

// 多项式转字符串(使用后需析构返回值)
char* PolynomialToString(Polynomial* p)
{
    char* str = (char*)malloc(100 * sizeof(char));
    memset(str, 0, 100 * sizeof(char));
    int index = 0;
    PolyNode* ptr = p->ptr;
    int is_head = 1;
    for (; NULL != ptr->next; ptr = ptr->next)
    {
        // 系数为0,不显示
        if (ptr->next->coe == 0)
        {
            continue;
        }
        // 如果不为开头,需要填上+和-
        if (!is_head)
        {
            if (ptr->next->coe < 0)
            {
                str[index++] = '-';
            }
            else
            {
                str[index++] = '+';
            }
        }
        // 如果为开头,需要考虑开头负号
        else
        {
            is_head = 0;
            if (ptr->next->coe < 0)
            {
                str[index++] = '-';
            }
        }
        // 如果该项为常量
        if (0 == ptr->next->deg)
        {
            char buf[100];
            itoa(abs(ptr->next->coe), buf, 10);
            strcat(str, buf);
            index += strlen(buf);
        }
        // 如果该项为变量
        else
        {
            char buf[100] = {0}, buf1[100] = {0};
            int buf_index = 0;
            if (abs(ptr->next->coe) != 1)
            {
                itoa(abs(ptr->next->coe), buf, 10);
            }
            buf[(buf_index = strlen(buf))++] = p->variable;
            buf[buf_index] = '\0';
            // 如果指数不为1,需要加上^和指数
            if (ptr->next->deg != 1)
            {
                buf[buf_index++] = '^';
                buf[buf_index] = '\0';
                itoa(ptr->next->deg, buf1, 10);
                strcat(buf, buf1);
            }
            strcat(str, buf);
            index += strlen(buf);
        }
    }
    if (index == 0)
    {
        str[index++] = '0';
    }
    str[index] = '\0';
    return str;
}
